package tree;

import tree.model.TreeNode;

import java.util.Stack;

///**
// *              8
// *            *   *
// *          4       12
// *        *   *     *  *
// *       1     5  10    14
// *            *
// *          3
// *   前序遍历：8,4,1,5,3,12,10,14
// *   中序遍历：1,4,3,5,8,10,12,14
// *   后续遍历：1,3,5,4,10,14,12,8
// *   层次遍历：8,4,12,1,5,10,14,3
// */
public class PostOrder {

    public static void main(String[] args) {
        postOrder1(genRoot1());
        System.out.println("");
        postOrder2(genRoot1());
    }

    public static void postOrder1(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder1(root.left);
        postOrder2(root.right);
        System.out.print(root.val + ",");
    }

    public static void postOrder2(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = null, pre = null;
        stack.push(root);
        while (!stack.isEmpty()) {
            cur = stack.peek();
            //下面是空节点，则需要出栈输出了
            if ((cur.left == null && cur.right == null)
                    //pre是他的左子节点或右子节点，说明他下面的已经出栈输出了，和下面是空节点没区别
                    || (pre != null && (pre == cur.left || pre == cur.right))) {
                System.out.print(cur.val + ",");
                stack.pop();
                pre = cur;
            } else {
                //因为先判断左边的，需要把右边先进栈，才能使得左边在栈上面
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
        }
    }

    public static TreeNode genRoot1() {

        TreeNode root = new TreeNode(8);
        TreeNode t4 = new TreeNode(4);
        TreeNode t12 = new TreeNode(12);
        TreeNode t1 = new TreeNode(1);
        TreeNode t5 = new TreeNode(5);
        TreeNode t10 = new TreeNode(10);
        TreeNode t14 = new TreeNode(14);
        TreeNode t3 = new TreeNode(3);
        root.left = t4;
        root.right = t12;
        t4.left = t1;
        t4.right = t5;
        t12.left = t10;
        t12.right = t14;
        t5.left = t3;
        return root;
    }
}
